/**
 * 描述：有些点不能走的Soldier
 *
 * @author wangb
 * @version 1.0
 * create 2018-11-04-23:48
 */
public class LittleSoldierWithSomeDiffcult{
    //格子的数目
    public static final int N = 7;
    public static final int M = 5;

    //不能走的点
    public static final int XNO = 3;
    public static final int YNO = 3;

    public static int[][]result;

    /**
     * 递归的解法
     * @param n
     * @param m
     * @return
     */
    public static int solve(int n ,int m){

        if(n == 0 || m == 0)
            return 1;
        if(n == XNO && m == YNO)
            return 0;
        if(result[n][m] >= 0)
            return result[n][m];

        result[n][m] = solve(n - 1,m) + solve (n ,m -1);
        return result[n][m];
    }

    /**
     * 迭代的解法
     * @param n
     * @param m
     * @return
     */
    public static int solveDitui(int n ,int m){

        for ( int i = 0 ; i <=N  ; i++ ) {
            result[i][0] = 1;
        }
        for ( int i = 0 ; i <=M  ; i++ ) {
            result[0][i] = 1;
        }

        for ( int i = 1 ; i <=N  ; i++ ) {
            for ( int j = 1  ; j <=M  ; j++ ) {
                if(i == XNO && j ==YNO)
                    result[i][j] = 0;
                else
                    result[i][j]  = result[i - 1][j] + result[i][ j - 1];
            }
        }
        return result[n][m];
    }

    public static void main(String[] args){
        result = new int[N + 1][M + 1];
        for ( int i = 0 ; i <=N  ; i++ ) {
            for ( int j = 0 ; j <=M  ; j++ ) {
                result[i][j] = -1;

            }
        }

        int s =solve (N,M);
        System.out.println ("递归的方法：");
        System.out.println (s);
        System.out.println ("迭代的方法：");
        s= solveDitui (N,M);
        System.out.println (s);

    }
}
